// 排序算法
#include <stdio.h>

/// @brief 交换a和b的值
/// @param a 数值a的指针
/// @param b 数值b的指针
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

/// @brief 冒泡排序
/// @param array 原始数组
/// @param length 数组长度
void bubbleSort(int array[], int length)
{
	int i, j;
	for (i = 0; i < length - 1; i++)
	{
		for (j = 0; j < length - i - 1; j++)
		{
			if (array[j] > array[j + 1])
			{
				swap(&array[j], &array[j + 1]);
			}
		}
	}
}

/// @brief 选择排序
/// @param array 原始数组
/// @param length 数组长度
void selectSort(int array[], int length)
{
	// 遍历下标和最小值的下标
	int i, j, min;
	for (i = 0; i < length; i++)
	{
		min = i;
		for (j = i + 1; j < length; j++)
		{
			if (array[j] < array[min])
			{
				min = j;
			}
		}
		swap(&array[i], &array[min]);
	}
}

/// @brief 插入排序
/// @param array 原始数组
/// @param length 数组长度
void insertSort(int array[], int length)
{
	int i, j, temp;
	for (i = 1; i < length; i++)
	{
		// 每一趟把当前项和前一项进行比较，若当前项小于前一项，则把当前项拿出，插入到前面最后一个比其大的后面
		if (array[i] < array[i - 1])
		{
			temp = array[i];
			for (j = i - 1; j >= 0 && array[j] > temp; j--)
			{
				// 往后移
				array[j + 1] = array[j];
			}
			// 插入
			array[j + 1] = temp;
		}
	}
}

/// @brief 希尔排序
/// @param array 原始数组
/// @param length 数组长度
void shellSort(int array[], int length)
{
	// 增量以及两个遍历下标，临时变量
	int increment = length, i, j, temp;
	do
	{
		// 每次把增量缩小为三分之一，按照增量间隔进行插入排序，并保证最后一趟增量一定是1
		increment = increment / 3 + 1;
		for (i = increment; i < length; i++)
		{
			// 每一趟按照增量间隔向前进行比较
			if (array[i] < array[i - increment])
			{
				temp = array[i];
				// 把比temp大的按照增量往后挪
				for (j = i - increment; j >= 0 && array[j] > temp; j -= increment)
				{
					array[j + increment] = array[j];
				}
				array[j + increment] = temp;
			}
		}
	} while (increment > 1);
}

/// @brief 堆调整：使之成为大根堆
/// @param heap 二叉树的顺序存储结构，为层次遍历存储，其中有一规律：若某节点的下标为i，那么其左孩子和右孩子的下标分别是2i + 1和2i + 2，i从0开始
/// @param start 开始调整的节点下标（双亲节点）
/// @param end 结束调整的节点下标（子节点）
void heapAdjust(int heap[], int start, int end)
{
	// 遍历下标，i即为每次比较时的较大的子节点，start则为其双亲节点
	int i;
	// 从开始节点的左孩子开始往下比较
	for (i = 2 * start + 1; i <= end; i = 2 * i + 1)
	{
		// 先选择左右孩子中较大的一个
		if (i < end && heap[i] < heap[i + 1])
		{
			i++;
		}
		// 和双亲节点比较
		if (heap[start] < heap[i])
		{
			// 交换两者的值使其成为大根堆
			swap(&heap[start], &heap[i]);
			// 以当前节点作为双亲节点继续向下比较
			start = i;
		}
	}
}

/// @brief 堆排序
/// @param array 原始数组
/// @param length 数组长度
void heapSort(int array[], int length)
{
	// 遍历下标
	int i;
	// 第一步：将原始无序列表构造成大根堆，从最后一个双亲节点开始进行调整，即整体上从下至上调整
	// 因为最后一个叶子节点下标是length - 1，设其双亲节点为i，所以可以得到2i + 1 = length - 1或者2i + 2 = length - 1，推出i = (length - 2) / 2或者i = (length - 3) / 2，而由于C语言中，整数相除向下取整，所以不论length - 1是左孩子还是右孩子，使用i = (length - 2) / 2都是适用的
	for (i = length - 2 / 2; i > 0; i--)
	{
		heapAdjust(array, i, length - 1);
	}
	// 第二步：把每一个最大的结点放到最后面去，然后对剩下第0到i - 1的节点进行重新构造成大根堆，i从最后一个往前移动
	// 堆调整完成后，最大的一定是根节点array[0]
	for (i = length - 1; i > 0; i--)
	{
		swap(&array[0], &array[i]);
		// 再次进行调整
		heapAdjust(array, 0, i - 1);
	}
}

/// @brief 对两部分有序的数组进行融合归并使之成为一个整体有序递增数组
/// @param array 部分有序的数组
/// @param start 第一部分有序的起始下标
/// @param mid 第一部分有序的终止下标
/// @param end 第二部分有序的终止下标
void merge(int array[], int start, int mid, int end)
{
	// array是部分有序的，即下标从start到mid是第一个有序的部分，第二部分下标就是mid + 1到end
	// 先把两部分复制到两个数组中
	// 左右两部分长度
	int leftLength = mid - start + 1, rightLength = end - mid;
	// 左右有序部分数组存放
	int left[leftLength], right[rightLength];
	// 遍历下标
	int i;
	for (i = 0; i < leftLength; i++)
	{
		left[i] = array[start + i];
	}
	for (i = 0; i < rightLength; i++)
	{
		right[i] = array[mid + 1 + i];
	}
	// 开始对原始数组的start到end融合归并
	// 左右辅助数组的下标
	int leftIndex = 0, rightIndex = 0;
	i = start;
	while (leftIndex < leftLength && rightIndex < rightLength)
	{
		// 小的归并进去
		if (left[leftIndex] <= right[rightIndex])
		{
			array[i++] = left[leftIndex++];
		}
		else
		{
			array[i++] = right[rightIndex++];
		}
	}
	// 检查是否还有剩余进行归并
	while (leftIndex < leftLength)
	{
		array[i++] = left[leftIndex++];
	}
	while (rightIndex < rightLength)
	{
		array[i++] = right[rightIndex++];
	}
}

/// @brief 归并排序的递归部分，对array的第start到end元素进行归并排序
/// @param array 原始数组
/// @param start 排序起始索引
/// @param end 排序终止索引
void mergeSortRecursive(int array[], int start, int end)
{
	// 递归结束：当划分得只剩下一个元素时
	if (start >= end)
	{
		return;
	}
	// 一分为二进行二路归并排序
	int mid = (start + end) / 2;
	mergeSortRecursive(array, start, mid);
	mergeSortRecursive(array, mid + 1, end);
	// 归并融合
	merge(array, start, mid, end);
}

/// @brief 归并排序递归版
/// @param array 原始数组
/// @param length 数组长度
void mergeSortR(int array[], int length)
{
	mergeSortRecursive(array, 0, length - 1);
}

/// @brief 把array分为若干个长度为subLength的子序列，然后对它们两两进行归并
/// @param array 原始数组
/// @param length 数组长度
/// @param subLength 每个子序列的长度
void mergePass(int array[], int length, int subLength)
{
	int count = length / subLength;	 // 子序列个数
	int groupCount = count / 2;		 // 第一次可被两两归并的子序列组数
	int remain = length % subLength; // 剩下没被整除的元素组成的最后一个子序列
	int i;							 // 遍历下标
	// 开始两两归并
	for (i = 0; i < groupCount; i++)
	{
		merge(array, 2 * i * subLength, (2 * i + 1) * subLength - 1, 2 * (i + 1) * subLength - 1);
	}
	// 再对剩下的没有归并完的部分进行归并处理
	if (count % 2 == 1 && remain != 0)
	{
		merge(array, 2 * groupCount * subLength, (2 * groupCount + 1) * subLength - 1, length - 1);
	}
}

/// @brief 归并排序迭代版
/// @param array 原始数组
/// @param length 数组长度
void mergeSort(int array[], int length)
{
	// 以subLength为子序列长度划分进行两两归并，初始时subLength为1
	int subLength;
	for (subLength = 1; subLength < length; subLength *= 2)
	{
		mergePass(array, length, subLength);
	}
}

/// @brief 在数组的low到high范围中选取一个枢轴变量，并把数组中比其小的移到枢轴变量前面，大的移到其后面，最后返回枢轴变量所在的索引，该函数使用三数取中法
/// @param array 原始数组
/// @param low 起始索引
/// @param high 终止索引
/// @return 最后枢轴变量位置
int partition(int array[], int low, int high)
{
	int mid = (low + high) / 2;
	// 先保证最右边比左边大
	if (array[high] < array[low])
	{
		swap(&array[low], &array[high]);
	}
	// 然后保证右边比中间大
	if (array[high] < array[mid])
	{
		swap(&array[mid], &array[high]);
	}
	// 最后把中等值换到左边
	if (array[low] < array[mid])
	{
		swap(&array[low], &array[mid]);
	}
	// 此时下标为low的变量为三数中间值，设为枢轴
	int pivot = array[low];
	while (low < high)
	{
		// 先开始，枢轴下标是low
		// 从后往前找到第一个比枢轴小的，使其和枢轴交换
		while (low < high && pivot <= array[high])
		{
			high--;
		}
		if (low < high)
		{
			swap(&array[low++], &array[high]);
		}
		// 交换后，枢轴下标变成了high
		// 这时再从前往后找到第一个大于枢轴的值进行交换
		while (low < high && pivot >= array[low])
		{
			low++;
		}
		if (low < high)
		{
			swap(&array[low], &array[high--]);
		}
		// 交换后，枢轴的下标又变回了low
	}
	return low;
}

/// @brief 快速排序的递归部分，对列表中索引为low到high这一部分元素进行快速排序
/// @param array 原始数组
/// @param low 起始索引
/// @param high 终止索引
void quickSortRecursive(int array[], int low, int high)
{
	int pivotIndex; // 枢轴变量的索引
	if (low < high)
	{
		pivotIndex = partition(array, low, high);
		quickSortRecursive(array, low, pivotIndex - 1);	 // 对枢轴之前的部分进行递归排序
		quickSortRecursive(array, pivotIndex + 1, high); // 对枢轴之后的部分进行递归排序
	}
}

/// @brief 快速排序
/// @param array 原始数组
/// @param length 数组长度
void quickSort(int array[], int length)
{
	quickSortRecursive(array, 0, length - 1);
}

int main()
{
	int array[] = {1, 4, 9, 5, 2, 12, 6, 134, 23, 122, 341, 27, 0, -12, 35, -9, 134, 90, -100, 2304};
	int length = sizeof(array) / sizeof(int), i;
	mergeSortR(array, length);
	for (i = 0; i < length; i++)
	{
		printf("%d ", array[i]);
	}
	return 0;
}